package algorithms.leaning.class24;

import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 假设一个固定大小为W的窗口，依次划过arr，
 * 返回每一次滑出状况的最大值
 * 例如，arr = [4,3,5,4,3,3,6,7], W = 3
 * 返回：[5,5,5,4,6,7]
 *
 * @author guichang
 * @date 2021/6/26
 */

@SuppressWarnings("all")
public class Code1_滑动窗口_窗口最大值 {

    public static void main(String[] args) {
        int[] array = MyUtil.createArray(4, 3, 5, 4, 3, 3, 6, 7);
        MyUtil.printInt(maxArray(array, 3));
    }

    public static int[] maxArray(int[] array, int W) {
        if (array == null || array.length < W || W < 1) {
            return null;
        }
        int N = array.length;
        // 最大值数组的长度为 N - W + 1
        int[] res = new int[N - W + 1];
        // res的索引
        int index = 0;
        // 双端队列，顺序始终从大到小，不可相等，首位为窗口的最大值
        Deque<Integer> deque = new ArrayDeque<>();
        for (int R = 0; R < N; R++) {
            int curr = array[R];
            // 弹出尾端小于等于curr的值
            while (!deque.isEmpty() && array[deque.peekLast()] <= curr) {
                deque.removeLast();
            }
            // 尾端增加当前坐标
            deque.addLast(R);
            // 弹出头
            if (deque.peekFirst() == R - W) {
                deque.removeFirst();
            }
            // 加入答案，前提是窗口已形成
            if (R - W + 1 >= 0) {
                res[index++] = array[deque.peekFirst()];
            }
        }
        return res;
    }
}